By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 38, Issue 4, pp. 1207-1659

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Fault-Tolerant Quantum Computation with Constant Error Rate

Dorit Aharonov and Michael Ben-Or

pp. 1207-1282

BibTeX  Abstract Full Text:  PDF

Mitotic Classes in Inductive Inference

Sanjay Jain and Frank Stephan

pp. 1283-1299

BibTeX  Abstract Full Text:  PDF

On Monotone Formula Composition of Perfect Zero-Knowledge Languages

Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, and Moti Yung

pp. 1300-1329

BibTeX  Abstract Full Text:  PDF

Network Failure Detection and Graph Connectivity

Jon Kleinberg, Mark Sandler, and Aleksandrs Slivkins

pp. 1330-1346

BibTeX  Abstract Full Text:  PDF

Resolution Is Not Automatizable Unless W[P] Is Tractable

Michael Alekhnovich and Alexander A. Razborov

pp. 1347-1363

BibTeX  Abstract Full Text:  PDF

Preservation under Extensions on Well-Behaved Finite Structures

Albert Atserias, Anuj Dawar, and Martin Grohe

pp. 1364-1381

BibTeX  Abstract Full Text:  PDF

Closest Substring Problems with Small Distances

Dániel Marx

pp. 1382-1410

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for Data Placement Problems

Ivan Baev, Rajmohan Rajaraman, and Chaitanya Swamy

pp. 1411-1429

BibTeX  Abstract Full Text:  PDF

Faster Algorithms for Minimum Cycle Basis in Directed Graphs

Ramesh Hariharan, Telikepalli Kavitha, and Kurt Mehlhorn

pp. 1430-1447

BibTeX  Abstract Full Text:  PDF

Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies

Subhash Khot and Assaf Naor

pp. 1448-1463

BibTeX  Abstract Full Text:  PDF

Combination Can Be Hard: Approximability of the Unique Coverage Problem

Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, and Mohammad R. Salavatipour

pp. 1464-1483

BibTeX  Abstract Full Text:  PDF

Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers

S. Kijima and T. Matsui

pp. 1484-1503

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for Biclustering Problems

Lusheng Wang, Yu Lin, and Xiaowen Liu

pp. 1504-1518

BibTeX  Abstract Full Text:  PDF

A Deterministic Subexponential Algorithm for Solving Parity Games

Marcin Jurdziński, Mike Paterson, and Uri Zwick

pp. 1519-1532

BibTeX  Abstract Full Text:  PDF

Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems

Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert E. Tarjan, and Jeffery R. Westbrook

pp. 1533-1573

BibTeX  Abstract Full Text:  PDF

The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement

Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal, and Corentin Travers

pp. 1574-1601

BibTeX  Abstract Full Text:  PDF

The Price of Stability for Network Design with Fair Cost Allocation

Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden

pp. 1602-1623

BibTeX  Abstract Full Text:  PDF

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Ran Raz, Amir Shpilka, and Amir Yehudayoff

pp. 1624-1647

BibTeX  Abstract Full Text:  PDF

Cost-Distance: Two Metric Network Design

Adam Meyerson, Kamesh Munagala, and Serge Plotkin

pp. 1648-1659

BibTeX  Abstract Full Text:  PDF